package 题目集.bfs._01bfs;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/description/
 */
public class 移除障碍的最小步数 {
    static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int minimumObstacles(int[][] grid) {
        // 记录到达每个位置的最小步数,在传统bfs中，visited数组记录是否访问过，这里用distance数组记录到达每个位置的最小步数。具有记录是否访问过的功能
        int[][] distance = new int[grid.length][grid[0].length];
        for (int[] ints : distance) {
            Arrays.fill(ints, Integer.MAX_VALUE);
        }
        ArrayDeque<int[]> deque = new ArrayDeque<>();
        distance[0][0] = 0;
        deque.add(new int[]{0, 0});
        while (!deque.isEmpty()) {
            int[] cur = deque.poll();
            if (cur[0] == grid.length - 1 && cur[1] == grid[0].length - 1) {
                return distance[cur[0]][cur[1]];
            }
            int d = distance[cur[0]][cur[1]];
            for (int[] dir : dirs) {
                int nx = cur[0] + dir[0];
                int ny = cur[1] + dir[1];
                if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && d + grid[nx][ny] < distance[nx][ny]) {     // 传统bfs中，这里是判断是否访问过
                    if (grid[nx][ny] == 0) {
                        deque.addFirst(new int[]{nx, ny});
                    } else {
                        deque.addLast(new int[]{nx, ny});
                    }
                    distance[nx][ny] = d + grid[nx][ny];
                }
            }
        }
        return distance[grid.length - 1][grid[0].length - 1];
    }

    @Test
    public void test() {
        int[][] grid = {{0, 1, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 1, 0}};
        int i = minimumObstacles(grid);
        System.out.println(i);
    }
}
